Celcom telah membawa perkhidmatan pelayaran mudah alih tanpa wayar sejak Perkhidmatan Peket Radio Umum atau (GPRS) diperkenalkan. GPRS memberikan pengguna kemudahan maya seperti perkhidmatan multimedia serta rangkaian Internet yang mudah alih. Perkhidmatan ini hanya memerlukan sokongan peranti seperti telefon bimbit, komputer dan sebagainya, tetapan yang diperlukan, serta kawasan yang telah ditetapkan. Kelajuan tertinggi yang dapat dicapai adalah 56 KB/s sahaja.

Sejak tahun 2005, Celcom telah memperkenalkan satu lagi perkhidmatan mudah alih tanpa wayar dan dinaiktaraf kepada perkhidmatan jalur lebar, iaitu 3G. Perkhidmatan 3G Celcom dilancarkan pada 17 Mei 2005, sempena Hari Telekomunikasi Sedunia. 3G merupakan perkhidmatan rangkaian mudah alih tanpa wayar yang dipertingkatkan daripada GPRS dan mampu mencapai kelajuan muat turun sehingga 384 KB/s serta pindah naik sehingga 64 KB/s. Perkhidmatan ini dapat memberikan keselesaan kepada pengguna untuk bergerak ke mana sahaja ke tempat-tempat yang ditawarkan liputan ini, dan juga sebagai alternatif kepada perkhidmatan jalur lebar berwayar seperti Streamyx. Setakat ini, perkhidmatan 3G ini ditawarkan oleh Celcom dan Maxis. Celcom turut memberikan perkhidmatan jalur lebar yang dinaiktaraf kepada 3.5G atau dipanggil Capaian Paket Pindah Turun Berkelajuan Tinggi atau HSDPA, yang memberikan kelajuan muat turun sehingga 3.6 MB/s.

Sehingga kini, Celcom merupakan pelayan perkhidmatan jalur lebar yang terbesar dan terluas di Malaysia. Pada peringkat awal, perkhidmatan ini ditawarkan meliputi bandar-bandar utama seperti di Lembah Klang, Pulau Pinang, Melaka, Johor Bahru, Genting Highlands dan Taman Teknologi Tinggi Kulim. Perkhidamatan 3G ini terus diluaskan ke merata tempat di negara seperti pada tahun 2006. Seperti pada 1 April 2006, Celcom sudah melancarkan rangkaian 3G di kawasan-kawasan seperti Kuching, Seremban, Alor Star, Sungai Petani, Tanjung Malim, Ipoh, Bukit Merah, Perak, Taiping, Kota Bharu, Kuantan, Perlis dan Kota Kinabalu.

Sejak tahun 2007, Celcom sedang berusaha untuk menawarkan perkhidmatan EDGE atau Nilai Data yang Dipertingkatkan Untuk Evolusi GSM kepada para pengguna, iaitu satu permulaan perkhidmatan jalur lebar yang mempertingkatkan muatan data ke dalam rangkaian GSM/GPRS, dan mempunyai ciri-ciri yang mematuhi garis panduan IMT-2000, ditetapkan oleh Kesatuan Telekomunikasi Sedunia atau ITU. EDGE turut dipanggil sebagai 2.75G. Perkhidmatan ini, di Celcom, hanya memerlukan Kad SIM yang menyokong perkhidmatan GPRS, tanpa perlu menaiktaraf kad tersebut, tidak seperti perkhidmatan 3G dan HSDPA. Untuk pemasangan sistem sokongan EDGE, Celcom telah melantik dua syarikat terkemuka dunia; Syarikat Alcatel-Lucent untuk memasang di Semenanjung Malaysia, dan syarikat Motorola bagi Malaysia Timur.